package com.chenxys.algorithm.leetcode;

import com.chenxys.algorithm.common.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * <p>
 *      给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。<br/>
 *      请你将两个数相加，并以相同形式返回一个表示和的链表。<br/>
 *      你可以假设除了数字 0 之外，这两个数都不会以 0 开头。<br/>
 *      示例： <br/>
 *          链表1: 2 -> 4 -> 3  == 342<br/>
 *          链表2: 5 -> 6 -> 4  == 465<br/>
 *          返回 : 7 -> 0 -> 8  == 807 <br/>
 * </p>
 *
 * @author Chenxys
 * @version V1.0
 * @Package com.chenxys.algorithm.leetcode
 * @date 2023/12/29 16:20
 * @Copyright ©
 */
@SuppressWarnings("all")
public class LeetCode02 {
    // 链表结构
    /*public static class ListNode {
        int val;
        ListNode next;

        public ListNode() {}

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }*/

    /**
     * <p>
     *     将两个链表逆序相加,并返回结过的逆序
     * </p>
     * @param l1 链表1
     * @param l2 链表2
     * @return 链表1逆序 + 链表2的结过
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 预指针,作用新建一个链表保存结果
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        // 进位值[若出现6 + 4 = 10, 那么进位就为1]
        int curry = 0;
        while (l1 != null || l2 != null){
            // 获取l1当前节点的值,如果l1当前节点为空返回0
            int x = l1 == null ? 0 : l1.val;
            // 获取l2当前节点的值,如果l2当前节点为空返回0
            int y = l2 == null ? 0 : l2.val;
            // 两数相加,再加上次的进位
            int sum = x + y + curry;
            // 进位重新取值 [因为两个数都是10以内,那么对两数和/10，可得十位数]
            curry = sum / 10;
            // 对当前两数和取个位值
            sum = sum % 10;
            cur.next = new ListNode(sum);
            // 当前节点指向下一个节点
            cur = cur.next;
            // 如果l1链表不为空,向下移动
            if (l1 != null) {
                l1 = l1.next;
            }
            // 如果l2链表不为空,向下移动
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        // l1 ,l2各个节点加完后进位不为0,再增加一个节点
        if (curry == 1) {
            cur.next = new ListNode(curry);
        }
        return pre.next;
    }

    public static ListNode checkAddTwoNumbers(ListNode l1, ListNode l2) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        while (l1 != null){
            list1.add(l1.val);
            l1 = l1.next;
        }
        while (l2 != null){
            list2.add(l2.val);
            l2 = l2.next;
        }
        ListNode pre = new ListNode(0);
        ListNode ans = pre;
        int curry = 0;
        if (list1.size() == list2.size()) {
            for (int i = 0; i < list1.size(); i++) {
                int sum = list1.get(i) + list2.get(i) + curry;
                curry = sum / 10;
                sum = sum % 10;
                ans.next = new ListNode(sum);
                ans = ans.next;
            }
        } else {
            int max = Math.max(list1.size(), list2.size());
            for (int i = 0; i < max; i++) {
                int sum = (i >= list1.size() ? 0 : list1.get(i)) + (i >= list2.size() ? 0 : list2.get(i)) + curry;
                curry = sum / 10;
                sum = sum % 10;
                ans.next = new ListNode(sum);
                ans = ans.next;
            }
        }
        if (curry == 1) ans.next = new ListNode(curry);
        return pre.next;
    }




    /**
     * <p>
     *     生成随机长度和随机大小的链表
     * </p>
     * @param maxSize 最大长度
     * @param maxval 最大值
     * @return 随机链表
     */
    /*public static ListNode generateRandomArr(int maxSize, int maxval) {
        int len = (int) ((Math.random()) * (maxSize + 1));
        ListNode cur = new ListNode((int) ((Math.random()) * (maxval + 1)));
        ListNode ans = cur;
        for (int i = 0; i < len; i++) {
            cur.next = new ListNode((int) ((Math.random()) * (maxval + 1)));
            cur = cur.next;
        }
        return ans;
    }*/

/*    public static void main(String[] args) {
        int maxSize = 50;
        int maxval = 100;
        int testTimes = 100000;
        System.out.println("Test Begin!");
        for (int i = 0; i < testTimes; i++) {
            ListNode listNode1 = generateRandomArr(maxSize, maxval);
            ListNode listNode2 = generateRandomArr(maxSize, maxval);
            ListNode ans1 = addTwoNumbers(listNode1, listNode2);
            ListNode ans2 = checkAddTwoNumbers(listNode1, listNode2);
            if (!checkListNode(ans1, ans2)) {
                System.out.println("Oops!");
                printList(ans1);
                System.out.println("--------");
                printList(ans2);
            }
        }
        System.out.println("Test Finish!");
    }*/

    public static void main(String[] args) {
        int maxSize = 50;
        int maxval = 100;
        int testTimes = 100000;
        System.out.println("Test Begin!");
        for (int i = 0; i < testTimes; i++) {
            ListNode listNode1 = ListNode.generateListNode(maxSize, maxval);
            ListNode listNode2 = ListNode.generateListNode(maxSize, maxval);
            ListNode ans1 = addTwoNumbers(listNode1, listNode2);
            ListNode ans2 = checkAddTwoNumbers(listNode1, listNode2);
            if (!ListNode.checkListNode(ans1, ans2)) {
                System.out.println("Oops!");
                ListNode.printNode(ans1);
                System.out.println("--------");
                ListNode.printNode(ans2);
            }
        }
        System.out.println("Test Finish!");
    }
}
